#include "myGraph.h"
#include <iostream>
#include <sstream>
#include <string>
#include <queue>

using namespace std;

EdgeNode::EdgeNode() {
	dest = -1;
	link = NULL;
}

EdgeNode::EdgeNode(int dest, EdgeNode* link){
	this->dest = dest;
	this->link = link;
}

EdgeNode::~EdgeNode(){
	dest = -1;
	link = NULL;
}

int EdgeNode::getDest(){
	return dest;
}

EdgeNode* EdgeNode::getNext(){
	return link;
}

void EdgeNode::setDest(int dest){
	this->dest = dest;
}

void EdgeNode::setNext(EdgeNode* link){
	this->link = link;
}

VertexNode::VertexNode(){
	data = -1;
	firstEdge = NULL;
}

VertexNode::VertexNode(char data, EdgeNode* firstEdge){
	this->data = data;
	this->firstEdge = firstEdge;
}

VertexNode::~VertexNode(){
	data = -1;
	EdgeNode* p = firstEdge;
	while (p != NULL)
	{
		EdgeNode* q = p;
		p = p->getNext();
		delete q;
	}
	firstEdge = NULL;
}

char VertexNode::getData(){
	return data;
}

EdgeNode* VertexNode::getFirstEdge(){
	return firstEdge;
}

void VertexNode::setData(char data){
	this->data = data;
}

void VertexNode::setFirstEdge(EdgeNode* firstEdge){
	this->firstEdge = firstEdge;
}

MyGraph::MyGraph(){
	nodeNum = 0;
	edgeNum = 0;
	VexList = NULL;
}

MyGraph::MyGraph(int nodeNum, int edgeNum, char* nodeList, int* edgeStartList, int* edgeEndList){
	this->nodeNum = nodeNum;
	this->edgeNum = edgeNum;
	VexList = new VertexNode[nodeNum];
	for (int i = 0; i < nodeNum; i++)
	{
		VexList[i].setData(nodeList[i]);
	}
	for (int i = 0; i < edgeNum; i++)
	{
		int startv = edgeStartList[i];
		int endv = edgeEndList[i];
		EdgeNode* p = new EdgeNode(endv, VexList[startv].getFirstEdge());
		VexList[startv].setFirstEdge(p);
		p = new EdgeNode(startv, VexList[endv].getFirstEdge());
		VexList[endv].setFirstEdge(p);
	}
}

MyGraph::~MyGraph(){
	nodeNum = 0;
	edgeNum = 0;
	delete[] VexList;
}

int MyGraph::getNodeNum(){
	return nodeNum;
}

int MyGraph::getEdgeNum(){
	return edgeNum;
}

string MyGraph::printGraph(){
	string graf;
	for (int i = 0; i < nodeNum - 1; i++)
	{
		graf += VexList[i].getData();
		graf.append(":");
		EdgeNode* p = VexList[i].getFirstEdge();
		while (p != NULL)
		{
			graf.append(" ");
			graf += VexList[p->getDest()].getData();
			p = p->getNext();
		}
		graf.append("\n");
	}
	graf += VexList[nodeNum - 1].getData();
	graf.append(":");
	EdgeNode* p = VexList[nodeNum - 1].getFirstEdge();
	while (p != NULL)
	{
		graf.append(" ");
		graf += VexList[p->getDest()].getData();
		p = p->getNext();
	}
	return graf;
}

int MyGraph::getFirstNeighbor(int v, int* visited){
	EdgeNode* p = VexList[v].getFirstEdge();
	while (p != NULL && visited[p->getDest()])
	{
		p = p->getNext();
	}
	if (p == NULL)
		return -1;
	else
		return p->getDest();
}

int MyGraph::getNextNeighbor(int v, int w, int* visited){
	EdgeNode* p = VexList[v].getFirstEdge();
	while (p->getDest() != w)
	{
		if (p != NULL && visited[p->getDest()])
		{
			p = p->getNext();
		}
		if (p == NULL)
			return -1;
	}
	while (p != NULL && visited[p->getDest()])
	{
		p = p->getNext();
	}
	if (p == NULL)
		return -1;
	else
		return p->getDest();
}

void MyGraph::DFS(int v, int* visited, string& result){
	result += VexList[v].getData();
	result += " ";
	visited[v] = 1;
	int w = getFirstNeighbor(v, visited);
	for (w; w != -1 && !visited[w]; w = getNextNeighbor(v, w, visited))
		DFS(w, visited, result);
}

string MyGraph::graph_DFS_Traverse(){
	string result = "";
	int* visited = new int[nodeNum];
	for (int i = 0; i < nodeNum; i++)
		visited[i] = 0;
	for (int v = 0; v < nodeNum; v++)
	{
		if (!visited[v])
			DFS(v, visited, result);
	}
	return result;
}

string MyGraph::graph_BFS_Traverse(){
	string result = "";
	int* visited = new int[nodeNum];
	for (int i = 0; i < nodeNum; i++)
		visited[i] = 0;
	queue<int> Q;
	for (int v = 0; v < nodeNum; v++)
	{
		if (!visited[v])
		{
			visited[v] = 1;
			result += VexList[v].getData();
			result += " ";
			Q.push(v);
			while (!Q.empty())
			{
				int u = Q.front();
				Q.pop();
				for (int w = getFirstNeighbor(u, visited); w != -1; w = getNextNeighbor(u, w, visited))
				{
					if (!visited[w])
					{
						visited[w] = 1;
						result += VexList[w].getData();
						result += " ";
						Q.push(w);
					}
				}
			}
		}
	}
	return result;
}
